package 比特教务管理系统.双链表;

public class 链表分割 {
    /**
     * （1）先令cur=head，把链表分成两段，第一段为小于目标值得，第二段为大于等于目标值的
     * （2）让cur遍历链表并判断节点放入哪一段里，直到cur==null；
     * （3）若cur.val<x，把cur尾插法到第一段里（分为是否第一次，如是第一次放进去就行了），若cur.val>=x，一样的方法
     * （4）循环结束后把第二段尾插到第一段最后就行了，返回bs
     * （5）最后要判断所有节点都在某一段的情况，若都在第二段，头结点就应是as
     * （6）在判断若第二段有节点，则要把第二段ae.next设为null，防止链表成环
     */
    public static MyDoubleLinkedList.Node Partition(MyDoubleLinkedList.Node pHead, int x){
        MyDoubleLinkedList.Node cur = pHead;
        MyDoubleLinkedList.Node smallStart = null;
        MyDoubleLinkedList.Node smallEnd = null;
        MyDoubleLinkedList.Node bigStart = null;
        MyDoubleLinkedList.Node bigEnd = null;

        while (cur != null){
            if (cur.data<x){
                if (smallStart == null){
                    smallStart = cur;
                    smallEnd = smallStart;
                }else {
                    smallEnd.next = cur;
                    smallEnd = smallEnd.next;
                }
            }else {
                if (bigStart == null){
                    bigStart = cur;
                    bigEnd = bigStart;
                }else {
                    bigEnd.next = cur;
                    bigEnd = bigEnd.next;
                }
            }
            cur = cur.next;
        }
        if (smallStart == null){
            return bigStart;
        }
        smallEnd.next = bigStart;
        if (bigStart != null){
            bigEnd.next = null;
        }
        return smallStart;
    }

    public static void main(String[] args) {
        MyDoubleLinkedList myDoubleLinkedList = new MyDoubleLinkedList();
        myDoubleLinkedList.insertLast(12);
        myDoubleLinkedList.insertLast(64);
        myDoubleLinkedList.insertLast(261);
        myDoubleLinkedList.insertLast(86);
        myDoubleLinkedList.insertLast(121);
        myDoubleLinkedList.insertLast(3);
        myDoubleLinkedList.displayAll();
        MyDoubleLinkedList.Node cur = Partition(myDoubleLinkedList.getHead(),90);
        while (cur!=null){
            cur.displayNode();
            cur = cur.next;
        }
    }
}
